\chapter{实验}
\label{chap:exp}

目前已介绍了GSL语言核心部分的设计与实现的所有内容。本章中将设计并开展相关实验，对该项目进行评价。本章的实验将分为两个部分：首先，对于GSL语言的设计进行评价，考察其表达能力以及对开发效率的提升；然后，对语言实现部分的双向匹配算法进行测试，对其时间复杂度进行评估。

\section{语言设计评价}
\label{sec:lang_eval}

\subsection{评价标准}

对一门程序语言进行的评价有若干标准，而对于领域特定语言，则主要关注其是否能有效地解决领域内的问题。对于计算图替换这一特定领域而言，最主要关心的问题就是其能否尽可能多地表达计算图的替换规则，即表达能力；以及是否能够减少表达这些规则所需要的工作量，即开发效率。

要考察语言的表达能力，可以从功能等价性入手。即使用GSL重新编写现有深度学习编译器中由开发者手工编写的、与图替换相关的编译器遍，考察GSL所编写的替换规则在功能上是否能与之等价。功能等价性可以从两个角度进行考察：一个角度是运行结果，即对于同一个输入的计算图，两种图替换的实现应该能给出一致的结果；另一个角度是代码结构，即两种实现方式的程序代码在结构上能够相互对应。本文中以前者作为主要的考察功能等价性的方式，同时也会兼顾后者。

要考察语言的开发效率，可以考虑比较手工编写的图替换遍与GSL编写的图替换规则所用的代码长度。代码长度可以一定程度上反映编写两种代码的所需的工作量，进而反映使用某种语言的开发效率。统计行数时，还需要注意以下问题：首先，由于深度学习编译器一般使用C++开发，而GSL目前设计为嵌入Python中的语言，不同语言语法会对行数产生影响。此外，各语言所编写图替换函数还可能调用其它函数，或图替换类可能继承自其它类，对此类情况也要进行处理。考虑上述因素，对代码行数统计的方式进行如下规定：

\begin{enumerate}
    \item 如果一行代码内含有除空格或任意一种括号（花括号、方括号、圆括号）之外的任何字符，则该行计入总行数；
    \item 每行代码不超过100个字符，超过的行应作换行处理并额外计数；
    \item 函数的声明、原型均不计入总行数；
    \item 断言、日志等和调试相关的代码均不计入总行数；
    \item 如果代码首次调用了其它函数，则被调用的函数也需要进行计数，任何被调用函数的代码行数仅统计一次；
    \item 如果代码以类的形式存在，仅统计其成员函数具体实现的代码，类的其它声明、定义均不计入；如果该类继承自某一父类，则父类中和图替换逻辑直接相关的代码需要计入。
\end{enumerate}

通过作这样的规定，可以尽可能地消除语言、编程规范等因素对于代码行数的影响，使统计出的结果尽可能地反映与核心逻辑直接相关的代码，提高数据的可比较性。

\subsection{实验方法}

本章中所进行的实验借助TVM\cite{chen2018tvm}深度学习框架的Relay\cite{roesch2019relay}中间表示语言开展。TVM的代码库\footnote{\url{https://github.com/apache/tvm/}}中包含了若干对于Relay语言的变换，其中有7个编译遍中的19种变换符合本文中所介绍的图替换的框架，本章的所有实验都围绕这些图替换展开，其具体内容在\ref{sec:lang_eval_result}节的实验结果中会逐一列出。TVM的代码库采用是ID为\texttt{b3ab19e}的版本，考虑到后续版本依然会添加新的替换，本文仅以该版本中的替换为准。

实验中对GSL进行了实现，核心部分包括3800行Python代码。该版本的GSL支持对Relay所描述的计算图进行改写，并且在第\ref{chap:design}章所描述的核心语言上进行了若干扩展，以支持更多样化的图结构与属性值计算。实验中将TVM代码库中所包括的图替换使用GSL重新编写，\ref{sec:lang_eval_result}节中关于GSL的实验结果均是在对此代码进行统计得到的。该GSL实现及相关实验代码已开源\footnote{\url{https://gitee.com/wzh99/gsl}}。

此外，实验中还将Relay中包含的DFP\cite{relay_pattern}加入统计并进行比较。DFP和GSL同样是用于图替换的嵌入式领域特定语言，在C++和Python中均可以使用其API。该语言本身仅支持计算图匹配，改写的过程需要手动编码。在TVM代码库所包含的编译器遍中，一部分也使用了该语言进行匹配。在对TVM中的代码进行考察时，如果含有使用了DFP的代码，这些代码认为是DFP的代码而不是纯粹的C++代码。如果没有现成代码，而该语言可以表达某个替换，则使用其Python的API编写该替换的代码。

\subsection{实验结果与分析}
\label{sec:lang_eval_result}

\subsubsection{功能}

本小节通过考察功能的等价性来评价语言的表达能力，表\ref{tab:func}展示了对上述19个替换使用不同的实现方式所完成的功能。``C++''是指不依赖其它领域特定语言，纯粹使用C++编写计算图替换的实现方式；``DFP''表示使用DFP进行匹配，并使用C++或Python编写改写程序的实现方式；``GSL''表示使用GSL编写替换规则的实现方式。表格中``无''表示没有相关代码可以进行比较；``完全''表示对于任意计算图都能完成预期的替换；``部分''表示仅在部分计算图上可得到预期的替换，在另一些计算图上则无法得到；``不能''表示该方式无法实现该替换。1-11号替换由于TVM代码库内的实现使用DFP进行匹配，故作为DFP统计，不存在纯粹使用C++编写的图替换。12-19号替换在代码库中包含纯粹使用C++编写的图替换，其中12-16号规则也可以用DFP进行实现。

\begin{table}[htb]
    \caption{各实现方式的所完成的图替换功能}
    \label{tab:func}
    \centering
    \begin{threeparttable}[b]
        \begin{tabular}{clccc}
            \toprule
            编号 & \makecell[c]{替换}                   & C++  & DFP  & GSL           \\
            \midrule
            1    & 具体化\texttt{zeros\_like}           & 无   & 完全 & 完全          \\
            2    & 具体化\texttt{ones\_like}            & 无   & 完全 & 完全          \\
            3    & 具体化\texttt{reshape\_like}         & 无   & 完全 & 完全          \\
            4    & 具体化\texttt{collapse\_sum\_like}   & 无   & 完全 & 完全          \\
            5    & 具体化\texttt{broadcast\_to\_like}   & 无   & 完全 & 完全          \\
            6    & 简化连续的\texttt{reshape}           & 无   & 完全 & 完全          \\
            7    & 简化连续的\texttt{transpose}         & 无   & 完全 & 完全          \\
            8    & 消去逐元素算子前的\texttt{full}      & 无   & 完全 & 完全          \\
            9    & 消去恒等运算                         & 无   & 完全 & 完全          \\
            10   & 消去卷积前的\texttt{pad}             & 无   & 完全 & 完全          \\
            11   & 将\texttt{bias\_add}转为\texttt{add} & 无   & 完全 & 完全          \\
            12   & 降级\texttt{batch\_norm}             & 完全 & 完全 & 完全          \\
            13   & 降级\texttt{layer\_norm}             & 完全 & 完全 & 完全          \\
            14   & 降级\texttt{group\_norm}             & 完全 & 完全 & 完全          \\
            15   & 降级\texttt{instance\_norm}          & 完全 & 完全 & 完全          \\
            16   & 降级\texttt{l2\_normalize}           & 完全 & 完全 & 完全          \\
            17   & 合并并行\texttt{conv2d}              & 完全\tnote{1} & 不能 & 部分\tnote{2} \\
            18   & 合并并行\texttt{dense}               & 完全\tnote{1} & 不能 & 部分\tnote{2} \\
            19   & 合并并行\texttt{batch\_matmul}       & 完全\tnote{1} & 不能 & 部分\tnote{2} \\
            \bottomrule
        \end{tabular}
        \begin{tablenotes}
            \item[1] TVM代码库的代码能完成其任务的前提是，计算图中不能包含某些算子，否则会产生断言错误而中途退出。GSL没有该限制。
            \item[2] GSL可以对任意计算图进行并行算子的合并，但无法像TVM中的代码那样同时合并其之后任意长的逐元素或广播算子链。
        \end{tablenotes}
    \end{threeparttable}
\end{table}

可以看到，GSL可以完整实现DFP所支持的所有源子图匹配，并且可以额外支持DFP所无法完成的匹配。17-19号匹配的源子图均是可变多输出顶点的模式，GSL能够支持此类模式，而DFP仅能支持单个输出顶点的模式匹配。这说明了在计算图替换中支持多输出模式与可变模式是有实际的应用价值的。GSL不能完全支持17-19号替换的原因在于，其无法匹配待合并算子之后任意长度的后继链。目前的框架下，GSL支持可变模式是水平的，即在元组字段或者模式图的输出顶点上可变，而不支持垂直的，即顶点的后继链上可变。

使用DFP实现的替换，其改写过程是使用C++/Python编写的。而GSL也可以完成相应的改写，这说明GSL在图改写方面达到了和通用编程语言几乎一致的表达能力。图的改写过程中，如何通过匹配的计算图求出目标计算图算子的属性是一个重要的问题。在这其中，属性表达式起到了重要的作用，它可以表达几乎所有的属性值的计算，其灵活性和可扩展性得到了充分的体现。

\subsubsection{代码长度}

本小节通过考察核心逻辑代码行数来考察GSL对于图替换程序开发效率的提升。表\ref{tab:line_count}展示了不同实现方式实现19个替换所需要的核心代码行数。如果该代码不存在或无法实现替换，则该位置空缺。如果某一实现方式只能实现部分的替换功能，则仅统计所有可用方式共同实现的功能所对应的代码。最后两列分别求了GSL的代码行数与C++或DFP代码行数的比值，以更直观地表现GSL减少代码行数的程度。

\begin{table}[htb]
    \caption{各实现方式实现相同功能所需核心代码行数}
    \label{tab:line_count}
    \centering
    \begin{tabular}{clccccc}
        \toprule
        编号 & \makecell[c]{替换}                   & C++  & DFP  & GSL & GSL:C++ & GSL:DFP \\
        \midrule
        1    & 具体化\texttt{zeros\_like}           & 无   & 8 & 4 & - & 0.50  \\
        2    & 具体化\texttt{ones\_like}            & 无   & 8 & 4 & - & 0.50  \\
        3    & 具体化\texttt{reshape\_like}         & 无   & 9 & 5 & - & 0.56  \\
        4    & 具体化\texttt{collapse\_sum\_like}   & 无   & 14 & 5 & - & 0.36\\
        5    & 具体化\texttt{broadcast\_to\_like}   & 无   & 9 & 5 & - & 0.56 \\
        6    & 简化连续的\texttt{reshape}           & 无   & 9 & 4 & - & 0.44 \\
        7    & 简化连续的\texttt{transpose}         & 无   & 46 & 13 & - & 0.28 \\
        8    & 消去逐元素算子前的\texttt{full}      & 无   & 35 & 14 & - & 0.40 \\
        9    & 消去恒等运算                         & 无   & 38 & 12 & - & 0.32 \\
        10   & 消去卷积前的\texttt{pad}             & 无   & 56 & 21 & - & 0.38 \\
        11   & 将\texttt{bias\_add}转为\texttt{add} & 无   & 23 & 11 & - & 0.48 \\
        12   & 降级\texttt{batch\_norm}             & 28 & 17 & 14 & 0.5 & 0.82 \\
        13   & 降级\texttt{layer\_norm}             & 22 & 22 & 16 & 0.72 & 0.73 \\
        14   & 降级\texttt{group\_norm}             & 41 & 29 & 23 & 0.56 & 0.79 \\
        15   & 降级\texttt{instance\_norm}          & 25 & 25 & 18 & 0.72 & 0.72 \\
        16   & 降级\texttt{l2\_normalize}           & 6 & 5 & 4 & 0.67 & 0.80 \\
        17   & 合并并行\texttt{conv2d}              & 98 & 不能 & 23 & 0.23 & - \\
        18   & 合并并行\texttt{dense}               & 76 & 不能 & 17 & 0.22 & - \\
        19   & 合并并行\texttt{batch\_matmul}       & 66 & 不能 & 17 & 0.26 & - \\
         & 平均 & - & - & - & 0.49 & 0.54 \\
        \bottomrule
    \end{tabular}
\end{table}

可以看到，无论是相比于纯粹的C++替换程序还是使用DFP进行匹配的图替换，GSL都能显著减少其代码量。还可以看到，替换的规则越复杂，GSL越能有效地减少代码行数。12-16号规则由于源模式图仅包含单个算子，故所能减少的代码量较为有限。17-19号规则包含可变输出顶点，手写的C++编译器遍需要先针对所关心的源子图实现一遍匹配的算法，而GSL直接运行通用匹配算法即可，这是代码行数差距较大的原因之一。此外，这三条规则涉及的算子属性也较多，GSL的属性表达式正好可以简练地表达算子属性的约束，这也使得GSL所需的代码行数更少。

本实验表明，在深度学习编译器的开发实践中，使用GSL描述计算图替换的结构，相比使用命令式语言描述图替换的具体算法，以及使用现有的图替换语言，均能够有效减少工作量。GSL的表达能力使其可以描述绝大部分的规则，只有很少的规则需要回退到命令式语言进行编写。这说明GSL达到了其设计的目的，能够起到增强表达能力与提高开发效率的作用。

\section{双向匹配算法测试}
\label{sec:alg_test}

GSL可以支持单输出、多输出、可变输出模式的替换。单输出模式只需要遍历一遍计算图就可以完成所有匹配子图的改写，其效率一定是较高的。而对于多输出模式与可变输出模式，\ref{sec:bidir_match}节中介绍了双向匹配算法，并对多输出模式的单次匹配给出较为具体的时间复杂度估计。在实际应用中，往往需要对所有匹配的子图进行替换，式\ref{eq:time_complexity}所描述的单次匹配复杂度显然不能准确描述实际应用中的运行时间。本节中将对双向匹配算法进行测试，对全部匹配时多输出模式以及可变输出模式的时间复杂度进行考察。

\subsection{实验方法}
\label{sec:alg_test_method}

本实验在不同模型上使用相应规则进行替换，以考察全部匹配时双向匹配算法的时间复杂度。由于匹配和改写这两个步骤关系密切，且改写的时间复杂度相比匹配而言较低（改写仅在匹配后才执行，和模式图规模呈线性关系），所以本实验通过测量整个替换过程的时间来考察匹配时间。对本节的实验均是在现实的深度学习模型上开展，更能反映算法在实际应用中的表现。本实验中所使用的模型有：Inception-v3\cite{szegedy2015rethinking}，一种卷积神经网络；NASNet-A\cite{zoph2018learning}，一种通过神经架构搜索（Neural Architecture Search，NAS）所得到的卷积神经网络；Transformer\cite{vaswani2017attention}，一种基于注意力机制的序列转换网络。

这些网络中，NASNet-A以及Transformer都可以通过改变超参数从而得到不同规模的网络：NASNet-A可以改变普通单元（Normal Cell）的数量，Transformer可以改变编码器（Encoder）和解码器（Decoder）内的层数。这些网络中分别具有一些多输出顶点的子图可以进行替换。NASNet-A中多个并行的ReLU运算可以合并；Transformer中多个并行的全连接层可以合并；Inception-v3中多个并行的卷积可以合并，其之后的偏置加以及再之后的ReLU可以进一步合并。

综合考虑上述网络的可扩展性，以及可使用的替换规则，对实验可进行如下设计：对于NASNet-A以及Transformer，其分别仅有一条规则可用，分别将该条规则定义为二输出、三输出、可变输出的形式，并改变网络的规模，测试不同计算图规及不同输出顶点数的改写耗时。对于Inception-v3，预先将其中的所有卷积-批归一化子图简化为卷积-偏置加，然后有三条规则可用，分别为仅合并卷积、合并卷积及偏置加、合并卷积及偏置加及ReLU，这三条规则内单个分支分别含有1、2、3个算子。将这三条规则也分别定义为二输出、三输出、可变输出的形式，测试不同输出顶点数量以及不同分支规模的改写耗时。由于本节主要考察的是双向匹配算法，所以所有涉及的规则都编写地尽可能简单，不会像\ref{sec:lang_eval}节中那样考虑替换规则的全面性，以减小属性求值等因素对运行时间的影响。

实验中所使用的GSL实现和\ref{sec:lang_eval}中相同。实验在Intel Core i5四核1.8GHz CPU、8GB RAM的计算机上运行，操作系统为Windows 10 20H2，Python版本为3.7。对于每个测试点运行五次求平均值，所有替换的结果均已检查过其正确性。

\subsection{实验结果与分析}
\label{sec:alg_test_result}

\begin{figure}[htbp]
    \centering
    \begin{subfigure}{7cm}
        \centering
        \includegraphics[width=\linewidth]{nasnet_a.pdf}
        \caption{NASNet-A}
    \end{subfigure}
    \begin{subfigure}{7cm}
        \centering
        \includegraphics[width=\linewidth]{transformer.pdf}
        \caption{Transformer}
    \end{subfigure}
    \caption{不同计算图规模、不同模式图输出顶点数时替换算法运行时间}
    \label{fig:graph_size}
\end{figure}

图\ref{fig:graph_size}中显示了对于NASNet-A以及Transformer进行替换测试的结果。从每条折线的形状可以看出，对于多次匹配，算法执行时间和计算图的规模依然近似为线性关系。比较同一张图中的各条直线，可以看到模式图的输出顶点数量对于整体运行时间的影响较小，并不与输出顶点的数量成倍数关系。还可以看到，可变输出模式的规则总是耗时最长的，这是因为可变输出模式往往匹配到的模式更多，对每个匹配到的模式都要进行改写，而不像固定输出顶点的模式只要找特定次数的匹配。但是可变输出模式匹配相比多输出模式并没有显著的时间增加，最多为20\%，平均不到10\%，且其变化趋势类似。这说明在现实的计算图中，可变模式匹配和多输出模式具有类似的复杂度。

另外可以注意到，在Transformer为1、2或5层时，二输出模式的耗时长于三输出。可能的原因是Transformer中有较多含3个并行全连接层的子图，当前实验要求算法执行所有替换后再结束，二输出模式对于此类子图需要尝试两次匹配并进行一次改写，三输出模式只需要尝试一次匹配并进行一次改写。在某些情况下，二输出模式的匹配可能需要更多时间。可见在全部匹配时，由于计算图自身结构的影响，模式图的输出顶点数更少不一定会使运行时间更短。

对比两图还可以看到，Transformer相比NASNet-A的算法运行时间对输出顶点的数目的变化更为敏感。这是因为Transformer所使用的合并并行全连接规则更为复杂，涉及的算子及属性约束更多，在匹配和改写上所花费的时间也会更多。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=9cm]{inception_v3.pdf}
    \caption{Inception-v3不同模式图输出顶点数、不同分支规模时替换算法运行时间}
    \label{fig:pattern_size}
\end{figure}

图\ref{fig:pattern_size}中显示了对Inception-v3模型测试的结果。观察其中各条折线，可以看到增加各分支内的算子数，即增加模式图的规模，匹配时间会有所增加，但其增加的幅度相比整体的匹配时间而言较小，在10\%至20\%之间。通过比较各条折线，也可以得到和图\ref{fig:graph_size}中类似的结论。同时还可以得出增加输出顶点数比增加模式图的规模对算法运行时间的影响更大，可达20\%以上，这是由于每增加一个输出顶点就要多进行一次双向匹配的迭代，而增加模式图的规模只需要在一次迭代中多匹配一些顶点而已。

从上述分析中可以得到，在全部匹配时，计算图的规模是匹配算法运行时间的决定性因素，且运行时间与计算图规模呈线性关系。此外，模式图输出顶点数、分支规模均会对算法运行时间产生影响，但这两个因素的变化对于算法运行时间的影响较小。如果用公式表达算法运行时间与模式图$G_p$及计算图$G_e$的大致关系，其应该具有下列形式
\begin{equation}
    \mathcal{O}((|V_e|+|E_e|)\cdot[1+\mathcal{F}(G_p)])
\end{equation}
该公式中$\mathcal{F}$是关于模式图$G_p$的函数，包含了输出顶点数、分支规模等影响模式图整体规模的因素，其值必小于$1$。

\paragraph{结论}本实验验证了双向匹配算法在时间复杂度上的高效性，为GSL的高效实现奠定了基础。在实践中，对于较大规模的计算图，以及可能较复杂的替换规则，替换算法的执行时间会在一个可接受的范围之内。这说明使用GSL进行图替换，并不会明显延长替换执行过程的耗时，具有在深度学习编译器中应用的可能性。

\section{本章小结}

本节进行了一些实验以对GSL的设计与实现进行评价。首先对GSL语言的设计进行评价，通过将GSL替换规则和纯C++替换程序以及使用DFP的替换程序在替换功能以及代码量的比较，考察了GSL在表达能力以及开发效率上的提升。然后，设计并开展了相关测试，考察GSL实现中关键的双向匹配算法在全部匹配时算法的时间复杂度，体现了该算法在时间复杂度上的高效性。